#include<iostream>
#include<algorithm>
#include<time.h>
#include<map>
#include<set>
using namespace std;

//01背包只有体积 1
class Solution {
public:
    /**
     * Note: 类名、方法名、参数名已经指定，请勿修改
     *
     * 
     * 
     * @param V int整型 货车的容量
     * @param item int整型vector 每个货物占用的体积
     * @return int整型
     */
    int bestFit(int V, vector<int>& item) {
        // write code here
        const int V1=V+1;
        //int*dp=new int[V1];
        //memset(dp,0,sizeof(dp));
        set<int>flag;
        for(int i=0;i<item.size();i++)
        {
            flag.insert(item[i]);
        }
        vector<pair<int,vector<int> >>dp;
        dp.resize(V1);
        for(int i=0;i<V1;i++)
        {
            dp[0].first=0;
        }
        dp[0].second=item;
        for(int i=1;i<V1;i++)
        {
            int tmpi=0;
            for(int j=0;j<dp[i-1].second.size();j++)
            {
                if(i-dp[i-g].first>=0)
                {
                    if(dp[i]<dp[i-g].first+g)
                    {
                        tmpi=j
                    }
                }
                dp[i-1].second.erase(dp[i-1].second+j,dp[i-1].second+j+1);
            }
            
        }
        return V-*max_element(dp,dp+V1);
    }
};

int main()
{

}
/*

全排列0.5
class Solution {
public:
    /**
     * Note: 类名、方法名、参数名已经指定，请勿修改
     *
     * 
     * 
     * @param V int整型 货车的容量
     * @param item int整型vector 每个货物占用的体积
     * @return int整型
     */
    int bestFit(int V, vector<int>& item) {
        // write code here
        const int V1=V+1;
        //int*dp=new int[V1];
        //memset(dp,0,sizeof(dp));
        sort(item.begin(),item.end());
        vector<vector<int>>dp;
        dp.resize(item.size());
        for(vector<int>&a:dp)
        {
            a.resize(V1);
        }
        for(int i=0;i<V1;i++)
        {
            if(i>=item[0])
            {
                dp[0][i]=item[0];
                continue;
            }
            dp[0][i]=0;

        }
        for(int i=0;i<item.size();i++)
        {
            dp[i][0]=0;
        }
        for(int i=1;i<item.size();i++)
        {
            for(int j=1;j<V1;j++)
            {
                if(j-item[i]>=0)
                {
                    dp[i][j]=max(dp[i-1][j-item[i]]+item[i],dp[i-1][j]);
                }
                else
                {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        int Max=0;
        for(int i=1;i<V1;i++)
        {
            Max=(Max,dp[item.size()-1][i]);
        }
        return V-Max;
    }
};

*/






class Solution {
public:
    /**
     * Note: 类名、方法名、参数名已经指定，请勿修改
     *
     * 
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
     void back(int i,string s,set<string>&se)
     {
         if(i==s.size())
         {
             if(se.count(s)==0)
             {
                 se.insert(s);
             }
             return;
         }
         for(int t=i;t<s.size();t++)
         {
             swap(s[t],s[i]);
             back(i+1,s,se);
             swap(s[t],s[i]);
         }
     }
    vector<string> permutation(string s) {
        // write code here
        
        vector<string>v;
        
        set<string>se;
        back(0,s,se);
        for(string q:se)
        {
            v.push_back(q);
        }
        //sort(v.begin(),v.end());
        return v;
    }
};
